class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0,maxn=INT_MIN;
        int n=nums.size();
        for(int i=0;i<n;i++){
            sum+=nums[i];
            maxn=max(maxn,nums[i]);
        }
        int target=sum/2;
        if(sum%2!=0||maxn>target)
            return false;
        vector<vector<bool>> rem(n,vector<bool>(target+1,false));
        for(int i=0;i<n;i++){
            rem[i][0]=true;
        }
        rem[0][nums[0]]=true;
        for(int i=1;i<n;i++){
            for(int j=1;j<=target;j++){
                if(j>nums[i])
                    rem[i][j]=rem[i-1][j]||rem[i-1][j-nums[i]];
                else
                    rem[i][j]=rem[i-1][j];
            }
        }
        return rem[n-1][target];
    }
};
